package com;

import java.util.ArrayList;
import java.util.Random;


public class Utilities {
	public class PowerLaw {

	    private Random rand;

	    /**
	     * constructs a power law object using an external random generator
	     */
	    public PowerLaw(Random r) {
	        rand = r;
	    }

	    /**
	     * constructs a power law object using an internal random generator
	     */
	    public PowerLaw() {
	        rand = new Random();
	    }

	    /**
	     * get uniformly distributed double in [0, 1]
	     */
	    public double getRand() {
	        return rand.nextDouble();
	    }

	    /**
	     * get uniformly distributed integer in [0, N - 1]
	     */
	    public int getRandInt(int N) {
	        return rand.nextInt(N);
	    }

	    /**
	     * selects item using power law probability of selecting array item: p(ni) =
	     * k * (ni^p) k is a normalisation constant p(ni) = 0 if ni is zero, even
	     * when p < 0
	     * 
	     * @param nums     array of numbers ni
	     * @param p        exponent p
	     * @return         index in [0, array size - 1]
	     */

	    public int select(double[] nums, double p) {
	        // make array of probabilities
	        double[] probs = new double[nums.length];
	        for (int i = 0; i < probs.length; i++) {
	            if (nums[i] == 0)
	                probs[i] = 0;
	            else
	                probs[i] = Math.pow(nums[i], p);
	        }

	        // sum probabilities
	        double sum = 0;
	        for (int i = 0; i < probs.length; i++) {
	            sum += probs[i];
	        }

	        // obtain random number in range [0, sum]
	        double r = sum * getRand();

	        // subtract probs until result negative
	        // no of iterations gives required index
	        int i;
	        for (i = 0; i < probs.length; i++) {
	            r -= probs[i];
	            if (r < 0) {
	                break;
	            }
	        }
	        return i;
	    }

	    /**
	     * select item using Zipf's law
	     * 
	     * @param size     of ranked array
	     * @return         index in [0, array size - 1]
	     */
	    public int zipf(int size) {
	        // make array of numbers
	        double[] nums = new double[size];
	        for (int i = 0; i < nums.length; i++) {
	            nums[i] = i + 1;
	        }
	        // get index using special case of power law
	        return select(nums, -1.0);
	    }

	    /**
	     * test purpose main
	     * 
	     * @param args
	     *            command line inputs
	     */

		public void run() {
		    //
		    PowerLaw p = new PowerLaw(new Random(555));
		
		    /*
		     * double[] numbers = {0, 1, 2, 3}; for (int i = 0; i < 5; i++) {
		     * System.out.println("Select: " + p.select(numbers, -1)); }
		     */
		    try {
		    	int N = 10000;
		    	int MAX = 100;
			    int numbers[] = new int[N];
			    for (int i = 0; i < N; i++) {
			    	int num = p.zipf(MAX);
			        //System.out.println("Zipf: " + num);
			        numbers[i] = num;
			    }
			    int histo[] = new int[MAX];
			    for(int i : numbers) { histo[i] += 1; }
			    for(int i = 0; i < MAX; ++i) { System.out.println(i + " : " + histo[i]); }
		    } catch(Exception e) {
		    	e.printStackTrace();
		    }
		}
	}
	public class CRC16Checksum {
		// CRC 16 checksum Look Up Table
		private int[] crc16_lut = {
	            0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
	            0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
	            0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
	            0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
	            0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
	            0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
	            0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
	            0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
	            0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
	            0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
	            0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
	            0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
	            0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
	            0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
	            0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
	            0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
	            0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
	            0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
	            0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
	            0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
	            0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
	            0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
	            0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
	            0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
	            0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
	            0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
	            0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
	            0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
	            0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
	            0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
	            0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
	            0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040,
	        };
		public int CRC16(String input) {
	        byte[] bytes = input.getBytes();
	        int crc = 0x0000;
	        for (byte b : bytes) {
	            crc = (crc >>> 8) ^ crc16_lut[(crc ^ b) & 0xff];
	        }
	        return crc;
		}
	    public void run() { 
	        int num_peers = 1000;
	        int divisor = 31;
	        // name peers
	        String prefix = "P";  // naming prefix, peers will be called "prefixN", for N : num_peers
	        ArrayList<String> names = new ArrayList<String>(num_peers); 
	        for(int i = 0; i < num_peers; ++i) {
	        	names.add(prefix + i);
	        }
	        // Calculate their DHT-key
	        for(String s : names) {
		        int d = divisor;
		        int crc = CRC16(s);
		        System.out.println("(CRC16(" + s + ") = " + crc + " ) % " + d + " = " + crc % d);
	        }
	    }
	}
	
	public static String init_network(int max_peers, int min_capa, int max_capa) {
		String ret = "\n# Initialize a network with " + max_peers + " peers with capa between " + min_capa + " and " + max_capa + "\n";
		int min = 8, max = 100, n = 50, vi = 0;
		int capas[] = com.PowerLaw.run(n*3, max);
		int viable[] =  new int[n * 3];

		for(int c : capas) {
			if(c >= min)
				viable[vi++] = c;
		}

		vi = 0;
		for(int c : viable) {
			if(vi >= n)
				break;
			if(c > 0) {
				String name = "P" + vi;
				int port = 50000 + vi;
				//spawn name address port capacity");
				ret += "spawn " + name + " 0 " + port + " " + c + "\n";
				//System.out.println("spawn " + name + " 0 " + port + " " + c);
				++vi;
			}
		}
		return ret;
	}
	
	public static String connect_network(int max_peers) {
		String ret = "";
		int i, port = 50000;
		// Introduce one to all
		ret += "\n# Introduce a single node to all \n";
		for(i = 0; i < max_peers; ++i) {
			ret += "control 0 " + port + " hello 0 " + (port + i) + "\n";
		}
		// Introduce all to him
		ret += "\n# Introduce all to that node \n";
		for(i = 0; i < max_peers; ++i) {
			ret += "control 0 " + (port + i) + " hello 0 " + port + "\n";
		}		
		return ret;
	}
	
	public static String create_overlay(int max_peers) {
		String ret = "";
		int i, port = 50000;
		ret += "\n# Tell every node to form an overlay network \n";
		for(i = 0; i < max_peers; ++i) {
			ret += "control 0 " + port + " overlay capacity \n";
		}
		return ret;
	}

	public static void main(String args[]) {
		int network_size = 50, min_capa = 10, max_capa = 50;
		System.out.println(init_network(network_size, min_capa, max_capa));
		System.out.println(connect_network(network_size));
		System.out.println(create_overlay(network_size));
		
		
	}
}